//https://www.nowcoder.com/practice/8b3b95850edb4115918ecebdf1b4d222?tpId=13&tqId=23250&ru=%2Fpractice%2Fb736e784e3e34731af99065031301bca&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking&sourceUrl=%2Fexam%2Foj%2Fta%3Fpage%3D1%26tpId%3D13%26type%3D13
// 逆向求解二叉树的高度,!!!!!!

#include <algorithm>
#include <climits>
#include <queue>
#include <vector>

using namespace std;

struct TreeNode {
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param pRoot TreeNode类 
     * @return bool布尔型
     */
    int GetNodeHeight(TreeNode* pRoot) {
        if (pRoot == nullptr) {
            return 0;
        }
        int height_left = GetNodeHeight(pRoot->left);
        int height_right = GetNodeHeight(pRoot->right);
        if (height_left == -1 || height_right == -1) return -1;
        if (abs(height_left - height_right) > 1) return -1;
        return max(height_left,height_right) + 1;

    }
    bool IsBalanced_Solution(TreeNode* pRoot) {
        // write code here
        if (pRoot == nullptr) return true; 
        int res = GetNodeHeight(pRoot);
        if (res == -1) return false;
        return true;
    }
};

struct ReturnData{
    bool isB_;
    int h_;
    ReturnData(bool isB,int h):isB_(isB),h_(h){
    }
};
class Solution2{
public:
    static ReturnData process(TreeNode* pRoot){
        if(pRoot == nullptr){
            return ReturnData(false,0);
        }
        auto leftData = process(pRoot->left);
        if(leftData.isB_==false){
            return ReturnData(false,0);
        }
        auto rightData = process(pRoot->right);
        if(rightData.isB_ == false){
            return ReturnData(false,0);
        }
        if(std::abs(rightData.h_-leftData.h_)>1){
            return ReturnData(false,0);
        }
        return ReturnData(true,std::max(leftData.h_,rightData.h_)+1);
    }
};